package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func flatten(root *TreeNode) {
	changeTree(root)
}

func changeTree(node *TreeNode) *TreeNode {
	var tail *TreeNode
	if node == nil {
		return tail
	}
	if node.Left == nil && node.Right == nil {
		tail = node
	}
	if node.Left != nil {
		tail = changeTree(node.Left)
		tail.Right = node.Right
	}
	if node.Right != nil {
		tail = changeTree(node.Right)
	}
	if node.Left != nil {
		node.Right = node.Left
		node.Left = nil
	}
	return tail
}
